package top.minuy.subject.costom.bfs;

import java.util.*;

/**
 * 有两个水桶，
 * 一个装5升，
 * 一个装3升。
 * 怎么利用这两个水桶，得到4升水?
 *
 * @author Minuy
 * @time 22:00
 * @date 2021/11/20
 */
public class WaterPuzzle {
    static class Solution1 {
        HashMap<Integer, Integer> pre;
        int t = 40, s = 0;

        public void bfs() {
            int sta = s;
            pre = new HashMap<>();
            ArrayList<Integer> queue = new ArrayList<>();
            queue.add(sta);
            pre.put(sta, sta);
            while (!queue.isEmpty()) {
                sta = queue.remove(0);

                ArrayList<Integer> nextSta = new ArrayList<>();

                {
                    int x = sta / 10;
                    int y = sta % 10;
                    int x1, y1, staNew;
                    // 下一个状态，x：5，y：3
                    // ------------------------------------
                    // 给桶1加水
                    x1 = 5;
                    y1 = y;
                    staNew = x1 * 10 + y1;
                    if (sta != staNew) {
                        nextSta.add(staNew);
                    }
                    // 给桶2加水
                    x1 = x;
                    y1 = 3;
                    staNew = x1 * 10 + y1;
                    if (sta != staNew) {
                        nextSta.add(staNew);
                    }
                    //-----------------------------
                    // 给桶1倒水
                    x1 = 0;
                    y1 = y;
                    staNew = x1 * 10 + y1;
                    if (sta != staNew) {
                        nextSta.add(staNew);
                    }
                    // 给桶2倒水
                    x1 = x;
                    y1 = 0;
                    staNew = x1 * 10 + y1;
                    if (sta != staNew) {
                        nextSta.add(staNew);
                    }
                    //------------------------
                    // 桶1->桶2
                    if (y + x <= 3) { // 没满出
                        y1 = x + y;
                        x1 = 0;
                    } else { // 满出
                        x1 = x - (3 - y);
                        y1 = 3;
                    }
                    staNew = x1 * 10 + y1;
                    if (sta != staNew) {
                        nextSta.add(staNew);
                    }
                    // 桶2->桶1
                    if (x + y <= 5) {
                        x1 = x + y;
                        y1 = 0;
                    } else {
                        x1 = 5;
                        y1 = y - (5 - x);
                    }
                    staNew = x1 * 10 + y1;
                    if (sta != staNew) {
                        nextSta.add(staNew);
                    }
                }

                for (Integer s : nextSta) {
                    if (!pre.containsKey(s)) {
                        queue.add(s);
                        pre.put(s, sta);
                        if (s == t) {
                            return;
                        }
                    }
                }
            }
        }

        public Iterable<Integer> process() {
            ArrayList<Integer> ret = new ArrayList<>();
            if (!pre.containsKey(t)) {
                return ret;
            }
            int cur = t;
            while (cur != s) {
                ret.add(cur);
                cur = pre.get(cur);
            }
            ret.add(s);

            Collections.reverse(ret);
            return ret;
        }
    }

    public static void main(String[] args) {
        Solution1 wp = new Solution1();
        wp.bfs();
        System.out.println(wp.process());

        Solution2 wp2 = new Solution2();
        for (String s : wp2.process()) {
            System.out.println(s);
        }
    }

    static class Solution2 {
        HashMap<Integer, String> describe;
        HashMap<Integer, Integer> pre;
        int t = 40, s = 0;

        public Solution2() {
            describe = new HashMap<>();
            pre = new HashMap<>();
            bfs();
        }

        public void bfs() {
            int sta = s;
            ArrayList<Integer> queue = new ArrayList<>();
            queue.add(sta);
            pre.put(sta, sta);
            while (!queue.isEmpty()) {
                sta = queue.remove(0);

                HashMap<Integer, String> nextSta = new HashMap<>();

                {
                    int x = sta / 10;
                    int y = sta % 10;
                    int x1, y1, staNew;
                    // 下一个状态，x：5，y：3
                    // ------------------------------------
                    // 给桶1加水
                    x1 = 5;
                    y1 = y;
                    staNew = x1 * 10 + y1;
                    nextSta.put(staNew, "给桶1加满水；");
                    // nextSta.add(staNew);

                    // 给桶2加水
                    x1 = x;
                    y1 = 3;
                    staNew = x1 * 10 + y1;
                    nextSta.put(staNew, "给桶2加满水；");
                    // nextSta.add(staNew);

                    //-----------------------------
                    // 给桶1倒水
                    x1 = 0;
                    y1 = y;
                    staNew = x1 * 10 + y1;
                    nextSta.put(staNew, "倒出桶1的水；");
                    // nextSta.add(staNew);

                    // 给桶2倒水
                    x1 = x;
                    y1 = 0;
                    staNew = x1 * 10 + y1;
                    nextSta.put(staNew, "倒出桶2的水；");
                    // nextSta.add(staNew);

                    //------------------------
                    // 桶1->桶2
                    if (y + x <= 3) { // 没满出
                        y1 = x + y;
                        x1 = 0;
                    } else { // 满出
                        x1 = x - (3 - y);
                        y1 = 3;
                    }
                    staNew = x1 * 10 + y1;
                    nextSta.put(staNew, "桶1的水倒入桶2；");
                    // nextSta.add(staNew);

                    // 桶2->桶1
                    if (x + y <= 5) {
                        x1 = x + y;
                        y1 = 0;
                    } else {
                        x1 = 5;
                        y1 = y - (5 - x);
                    }
                    staNew = x1 * 10 + y1;
                    nextSta.put(staNew, "桶2的水倒入桶1；");
                    // nextSta.add(staNew);

                }

                for (Integer s : nextSta.keySet()) {
                    if (!pre.containsKey(s)) {
                        queue.add(s);
                        pre.put(s, sta);
                        describe.put((s * 100) + sta, nextSta.get(s));
                        if (s == t) {
                            return;
                        }
                    }
                }
            }
        }

        public Iterable<String> process() {
            ArrayList<Integer> ret = new ArrayList<>();
            if (!pre.containsKey(t)) {
                return new ArrayList<>();
            }
            int cur = t;
            while (cur != s) {
                ret.add(cur);
                cur = pre.get(cur);
            }
            ret.add(s);

            Collections.reverse(ret);

            ArrayList<String> res = new ArrayList<>();
            int s = ret.get(0);
            for (int i = 1; i < ret.size(); i++) {
                res.add("当前状态：[" + (s / 10) + "],[" + (s % 10) + "]");
                int sNext = ret.get(i);
                res.add("第" + i + "步操作：" + describe.get((sNext * 100) + s));

                s = sNext;
            }

            res.add("当前状态：[" + (s / 10) + "],[" + (s % 10) + "]");

            return res;
        }
    }


}
